<?php
/**
 ***** 扶摇而上、抱守本真 ******
 * @author Dana
 * @Date 2021/7/15
 */

/**
 *
 * 最近公共祖先
 * 给定一个二叉树，找到该树中两个节点的最近公共祖先  q,p
 * 直接搜索 给定节点
 * 如果 左右都有 那就是 根节点
 * 如果都在左边，那么 右边就是空
 * 如果在右边，那么 左边就是空
 * Class CommonAncestor
 * @author Zhoufurong
 * @Date 2021/7/15
 */
class CommonAncestor{

    public function lowestCommonAncestor($root,$p,$q)
    {
        if($root == null) return null;
        if($root == $q || $root == $q){
            return $root; // 既然肯定有 ，而且有一个是根，那么直接返回根
        }
        // 如果上面没有，那么在左右两边
        // 根节点往下一层找，直到找到与两个一个相等为止
        $left = $this->lowestCommonAncestor($root->left,$p,$q);
        $right = $this->lowestCommonAncestor($root->right,$p,$q);
        // 有三种情况，如果同在 左边，那么肯定 右边为空
        // 如果同在右边，那么 左边为空
        // 如果两边都不为空 那么肯定根节点

        if($left && $right) return $root;
        return $left ? $left : $right;
    }
}